The present invention relates to a compiler which analyzes source programs and produces object programs using a computer, and more particularly to a method of producing object programs suitable for optimization of a source program which contains calling of procedures (procedure call).
A function of a compiler to produce an object program so as to allow it high speed operation is called optimization. Conventionally, optimization has been allowed to be applied only within one procedure such as a subroutine, function and the like. However, recently, interprocedural optimization has been used, as discussed in "Direct Parallelization of CALL statements", Proceedings of the SIGPLAN 86 Symposium on Compiler Construction, SIGPLAN Notices Vol. 21, No. 7, July, 1986, pp. 176 to 185. In this paper, a method of analyzing array references interprocedurally is discussed which is necessary to judge if a loop containing a procedure call can be executed in parallel. According to this method, the procedure call effect is summarized into the information named region which indicates the part of an array referenced in a procedure. In fact this method, can analyze two kind of regions. One is the region as a part of an array whose values may be modified upon a procedure call. And the other is the region as a part of an array whose values may be used upon a procedure call. In parallelization of a loop containing a procedure call, if there is no overlap among regions which may be referenced at each iteration of the loop, then it is judged that the loop can be executed in parallel. More precisely, it is analyzed if there is overlap between a certain region which may have modified values at a certain iteration of the loop, and another region which may have modified or used values at another iteration of the loop. If there is no overlap, then it is judged that each iteration of the loop can be executed in parallel at the same time.
The above-described prior art, however, is directed to a problem of lowering the capability of optimization when the same region is referred to plural times. For instance, consider the program shown at the left side in FIG. 20 wherein V is referred to at 4-th and 7-th lines of ISN in subroutine SUB1. Since all, elements of array V are redefined each time subroutine SUB2 is called at 4-th line of ISN in the subroutine SUB1, the values of the elements of array V are used independently on each value of control variable J of DO 10. Therefore, by extending the dimension of V as shown at the right side in FIG. 20, DO 10 can be executed in parallel for respective values of J. With this parallelization of the loop, the execution speed of the program module becomes as fast as 100 times, at a maximum, that of a conventional one wherein the loop is repeated 100 times from J=1 to J=100. However, with the prior art method, only the possibility of modifying or using values of array V at each iteration of the DO 10 loop at SUB1 is analyzed, and it is not known that a definition is always performed prior to the use of array V. Thus, it is impossible to effect such optimization.
As other prior art, U.S. patent application Ser. No. 15,018 (filed on Feb. 17, 1987) "Compiler code optimization method for a source program having a first and second array definition and use statements in a loop", now U.S. Pat. No. 4,773,007, is associated with the present invention. The prior art shown in U.S. Pat. No. 4,773,007 is a dataflow analysis technology as to elements of array, and the scope of analysis is limited to be within a loop of one procedure, but by taking into consideration the control flow in a procedure, a data flow among reference points of array elements can be analyzed precisely. That is, in the prior art, by investigating reference of array elements successively along execution order of the program within a loop, it is possible to carry out analysis distinguishing possibility and necessity such that a value of array element defined in a statement reaches another statement without being defined on the way, or that only that value reaches the other element. But, in the prior art, the subject of the analysis is only elements of array, and the scope of analysis is limited to be only within a procedure.